﻿using System.Collections.Generic;

namespace Collatz
{
    /// <summary>
    /// 表示不使用<see cref="CollatzSerial"/>的解算方法
    /// </summary>
    public class NonInstanceSolver : Solver
    {
        /// <summary>
        /// 用指定的最大数值创建一个实例
        /// </summary>
        /// <param name="start">最大数值，从此数值开始向递减方向解算</param>
        /// <exception cref="ArgumentOutOfRangeException">当<paramref name="start"/>不是正整数时引发</exception>
        public NonInstanceSolver(int start)
            : base(start)
        {
            _dictionary = new Dictionary<long, int>() { { 1, 1 } };
        }

        private readonly Dictionary<long, int> _dictionary;

        public override int Solve()
        {
            var maxStart = 0;
            var maxCount = 0;
            for (var i = _start; i > 0; i--)
            {
                var count = Count(i);
                if (count > maxCount)
                {
                    maxStart = i;
                    maxCount = count;
                }
            }
            return maxStart;
        }

        /// <summary>
        /// 获取以指定数值为开头的序列长度
        /// </summary>
        /// <param name="start">以此数值作为序列开头</param>
        /// <returns>序列长度</returns>
        private int Count(long start)
        {
            if (_dictionary.ContainsKey(start))
            {
                return _dictionary[start];
            }
            else
            {
                var length = 1 + Count(start % 2 == 0 ? start / 2 : start * 3 + 1);
                _dictionary.Add(start, length);
                return length;
            }
        }
    }
}
